package org.hit.burkun.swalk;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

import cern.colt.function.tdouble.DoubleDoubleFunction;
import cern.colt.matrix.tdouble.DoubleMatrix1D;
import cern.colt.matrix.tdouble.impl.DenseDoubleMatrix1D;
import cern.jet.math.tdouble.DoubleFunctions;

/**
 * 
 * Abstract class for graph implementation
 *
 */
public abstract class RandomWalkGraph {
	/**Number of nodes */
	public int dim;                                              
	/**The starting node*/
	public int s;                                         
	/**Number of features per node*/
	public int f;                                                
	/**The graph*/
	public ArrayList<FeatureField> list;                         
	/**The future links set*/
	public ArrayList<Integer> D;     
	/**The future no-link set*/
	public ArrayList<Integer> L; 
                          
	
	// useful
	/**Pagerank*/
	public DoubleMatrix1D p;                                     
	/**Pagerank gradient*/
	public DoubleMatrix1D [] dp;                                 
	
	
	/**
	 * Constructor
	 * 
	 * @param dim: number of nodes
	 * @param s: the starting node
	 * @param f: the number of features
	 * @param list: the graph as list of FeatureFields
	 * @param D: the future-links set
	 * @param L: the no-links set
	 */
	public RandomWalkGraph(int dim, int s, int f, ArrayList<FeatureField> list,
			ArrayList<Integer> D, ArrayList<Integer> L) {
		this.dim = dim; //节点个数
		this.s = s;
		this.f = f; //特征数量
		this.list = list;  //特征矩阵，N*N*f
		this.D = D; //正例
		this.L = L; //负例
		this.p = new DenseDoubleMatrix1D(this.dim);
		this.dp = new DoubleMatrix1D [this.f];  //每个权值的偏导
		for (int i = 0; i < this.f; i++)
			dp[i] = new DenseDoubleMatrix1D(this.dim); //每个点，每个权值偏导
	}
	
	
	/**
	 * Constructor
	 */
	public RandomWalkGraph () {};


	/**
	 * Build the adjacency matrix of the graph given parameters
	 * 
	 * @param param: the parameters used for building the adjacency matrix
	 */
	public abstract void buildAdjacencyMatrix (DoubleMatrix1D param); 
	
	
	/**
	* Build the transition matrix for given adjacency matrix
	*
	* @param alpha: damping factor
	* @return SparseCCDoubleMatrix2D
	*/
	public abstract ArrayList<HashMap<Integer, Double>> buildTransitionTranspose (double alpha);
	
	
	/**
	 * Returns matrix of partial derivatives of the transition matrix
	 *  with respect to the featureIndex-th parameter for the given graph 
     * 
	 * @param featureIndex: the index of the parameter with respect to which the derivative is being calculated 
	 * @param alpha: the damping factor
	 * @return SparseCCDoubleMatrix2D
	 */
	public abstract ArrayList<HashMap<Integer, Double>> transitionDerivativeTranspose (int featureIndex, double alpha, DoubleMatrix1D param);
	
	
	/**
	 * Defines the edge-weighting function
	 * 
	 * @param x: weighting function argument
	 * @return double
	 */
	public abstract double weightingFunction (double x);
	
	
	/**
	 * Calculate partial derivative of the weight function (exponential funcion 
	 * considered) parameterized by w, with respect to the index-th parameter
	 * for the given graph
	 * 
	 * @param nodeIndex: the index of the node in the graph
	 * @param row: the row index of the adjacency matrix
	 * @param column: the column index of the adjacency matrix
	 * @param featureIndex: the index of the parameter with respect to which the derivative is being calculated 
	 * @return double
	 */
	public abstract double weightingFunctionDerivative (double x, double featureValue);
	
	
	/**
	 * Returns true if a link from 'from' node to 'to' node in the graph,
	 * otherwise returns false
	 * 
	 * @param from: link start node
	 * @param to: link end node
	 * @return boolean
	 */
	public abstract boolean hasLink (int from, int to);
	
	
	
	
	/**
	 * Calculates pagerank and it's gradient, for given graph index
	 *  
	 * @param param: the parameters for building the adjacency matrix
	 * @param alpha: the damping factor
	 */
	public void pageRankAndGradient (DoubleMatrix1D param, double alpha, double eps) {
		//System.out.println("init adj..");
		buildAdjacencyMatrix(param);
		//System.out.println("init Qt..");
		ArrayList<HashMap<Integer, Double>> Qt = buildTransitionTranspose(alpha);
		//debug
		//System.out.println("Qt is full one" + isFullOne(Qt));
		//更改，进行一次pr
		//double EPSILON = 1e-6;
		double EPSILON = eps;
		DoubleMatrix1D oldP = new DenseDoubleMatrix1D(dim);        // the value of p in the previous iteration
		DoubleMatrix1D oldDp = new DenseDoubleMatrix1D(dim);       // the value of dp in the previous iteration
		                                                           // ...starts with all entries 0 
		boolean [] dpConverged = new boolean [f];
		boolean allDpConverged = false;
		boolean pConverged = false;
		p.assign(1.0 / dim); 
		for (int k = 0; k < f; k++){                           // for every parameter
			dp[k].assign(DoubleFunctions.constant(0));
		}//设置初值为0
		DoubleMatrix1D tmp = new DenseDoubleMatrix1D(dim);
		ArrayList<ArrayList<HashMap<Integer, Double>>> tdt = new ArrayList<>(f);

		for (int k = 0; k < f; k++){
			//计算qt
			//System.out.println("transitionDerivativeTranspose Qt.." + k);
			tdt.add(k, transitionDerivativeTranspose(k, alpha, param));
		}
		//int counter = 0;
		//计算p/w, power method
		while (!allDpConverged) {
			allDpConverged = true;
			//System.out.println(Thread.currentThread() + " do iter in power methods..." + (counter++));
			if (!pConverged) {
				oldP.assign(p);
				p = zMult(Qt, oldP);	
//				p.normalize();
				oldP.assign(p, new DoubleDoubleFunction() {
					@Override
					public double apply(double arg0, double arg1) {
						return Math.abs(arg0-arg1);
					}
				});
				double errorSums = oldP.zSum();
				if (errorSums < EPSILON)
					pConverged = true;
			}
			
			for (int k = 0; k < f; k++) {
				if (dpConverged[k]) continue;
				//迭代求pwk的过程
				oldDp.assign(dp[k]);
				tmp = zMult(tdt.get(k), p);
				//tdt[k].zMult(p, tmp);
				dp[k] = zMult(Qt, oldDp);
				//Qt.zMult(oldDp, dp[k]);
				dp[k].assign(tmp, DoubleFunctions.plus);
				oldDp.assign(dp[k], new DoubleDoubleFunction() {
					@Override
					public double apply(double arg0, double arg1) {
						return Math.abs(arg0-arg1);
					}
				});
				double oldDpSum = oldDp.zSum();
				//System.out.println(Thread.currentThread() + " dpr error: " + (oldDpSum));
				if (oldDpSum < EPSILON)
					dpConverged[k] = true;
				else
					allDpConverged = false;
			}
		}
	}
	
	//add to make global par
	
	
	
	//debug
	public boolean isFullOne(ArrayList<HashMap<Integer, Double>> matrix){
		double rsum[] = new double[dim];
		for(FeatureField ff : list){
			int r = ff.row;
			int c = ff.column;
			rsum[r] += matrix.get(c).get(r);
		}
		for(int i=0; i<dim; i++){
			if(rsum[i] - 1 > 1e-2){
				return false;
			}
		}
		return true;
	}
	
	public static DoubleMatrix1D zMult(ArrayList<HashMap<Integer, Double>> matrix, DoubleMatrix1D pp){
		DoubleMatrix1D temp = new DenseDoubleMatrix1D(matrix.size());
		for(int i=0; i<matrix.size(); i++){
			HashMap<Integer, Double> row = matrix.get(i);
			Set<Entry<Integer, Double>> entires = row.entrySet();
			double sums = 0;
			for(Entry<Integer, Double> entry : entires){
				int col = entry.getKey();
				double score = entry.getValue();
				sums += score * pp.get(col);
			}
			temp.set(i, sums);
		}
		return temp;
	}
}
